package com.zm.demo.core.leetcode;

import static java.lang.System.out;

/**
  @author zoum
  @create 2020/1/9 13:45
 */
public class PathSum3 {
    int total = 0;
    public int pathSum(TreeNode root, int sum) {
        if (root != null){
            calc(root, sum);
            if (root.left != null){
                pathSum(root.left, sum);
            }
            if (root.right != null){
                pathSum(root.right, sum);
            }
        }
        return total;

    }

    public void calc(TreeNode node, int calSum){
        calSum -= node.val;
        if (calSum == 0 ){
            total ++;
        }

        if (node.left != null){
            calc(node.left, calSum);

        }

        if (node.right != null){
            calc(node.right, calSum);
        }
    }

    public static void main(String[]args){

        TreeNode node4_1 = new TreeNode(3);
        TreeNode node4_2 = new TreeNode(-2);
        TreeNode node3_1 = new TreeNode(3);
        node3_1.left=node4_1;
        node3_1.right=node4_2;

        TreeNode node4_3 = new TreeNode(1);
        TreeNode node3_2 = new TreeNode(2);
        node3_2.right=node4_3;

        TreeNode node2_1 = new TreeNode(5);
        node2_1.left = node3_1;
        node2_1.right = node3_2;

        TreeNode node3_3 = new TreeNode(11);
        TreeNode node2_2 = new TreeNode(-3);
        node2_2.right = node3_3;
        TreeNode node1 = new TreeNode(10);
        node1.left = node2_1;
        node1.right = node2_2;
//        TreeNode node1 = new TreeNode(1);
//        TreeNode node2 = new TreeNode(2);
//        TreeNode node3 = new TreeNode(3);
//        TreeNode node4 = new TreeNode(4);
//        TreeNode node5 = new TreeNode(5);
//        node1.right = node2;
//        node2.right = node3;
//        node3.right = node4;
//        node4.right = node5;


        out.println(new PathSum3().pathSum(node1, 8));






    }
}


